package com.yiguang.algorithm.backtracking;

import java.util.ArrayList;
import java.util.List;

import com.sun.xml.internal.ws.policy.privateutil.PolicyUtils.Collections;

/*
77. 组合
39. 组合总和
40. 组合总和 II
46. 全排列
47. 全排列 II
78. 子集
90. 子集 II
27. 回文链表
 */
public class BacktrackingAlgorithm {
	public static void main(String[] args) {
		System.out.println(combine(5, 3));
	}
	
	/**
	77. 组合
	给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
	你可以按 任何顺序 返回答案。5,3
	输入：n = 4, k = 2
	输出：
	[
	  [2,4],
	  [3,4],
	  [2,3],
	  [1,2],
	  [1,3],
	  [1,4],
	]
	*/
	public static List<List<Integer>> combine(int n, int k) {
		List<List<Integer>> result = new ArrayList();
		List<Integer> currentResult = new ArrayList();
		backtrack(result, currentResult, n, k, 1);
		return result;
    }

	private static void backtrack(List<List<Integer>> result, List<Integer> currentResult, int n, int k, int index) {
		// 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp
	    if (currentResult.size()+(n-index+1) < k) {
	        return;
	    }
		for(int i=index; i<=n; i++) {
			List<Integer> temp = new ArrayList(currentResult);
			if(temp.size()+1 == k) {
				temp.add(i);
				result.add(temp);
				continue;
			}
			temp.add(i);
			backtrack(result, temp, n, k, i+1);
		}
	}

	// 子集
	public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList();
        List<Integer> middle = new ArrayList();
        result.add(middle);
        combime(result, middle, nums, 0);
        return result;
    }  
	//1 2 3 4 5
    public void combime(List<List<Integer>> result, List<Integer> middle, int[] nums, int begin) {
        for(int i=begin; i<nums.length; i++) {
            List<Integer> data = new ArrayList(middle);
            data.add(nums[i]);
            result.add(data);
            combime(result, data, nums, i+1);
        }
    }

    // 27. 回文链表
    public boolean isPalindrome(ListNode head) {
    	return true;
    }
    
}
